Hash and Message Authentication Code (or MAC) algorithms are extremely important and, at the same time, the most vulnerable components of network security. These algorithms are used to provide a hash or MAC value that can serve as authentication of the integrity of a message that they have been appended to. A recipient user can perform the same hash or MAC operation on the received data to obtain a hash or MAC value and to compare it with appended value in order to verify that the data has not been modified in transit. It should be noted that because hash and MAC algorithms produce tags of a fixed size for inputs of all lengths, the mapping is a many-to-one mapping, which results in “hash collisions”. Hash collisions result when two different messages have the same hash or MAC value. The design of the algorithms is intended to generate widely divergent hash or MAC values for slightly different inputs which provide an ease of recognizing of message alteration.
A typical secure hash function is generally referred to as an iterated hash function and is based on a proposal by Merkle (R. C. Merkle, Authentication and Public Key systems, Ph. D. Thesis, Stanford University, June 1979, and R. C. Merkle, One way hash functions and DES, in: Advances in Cryptology—Crypto '89, ed. Brassard, pp. 428-446, Lecture Notes in Computer Science 435, Springer-Verlag, 1990). According to Merkle's proposal, the hash function takes an input string of bits and partitions the string into fixed-sized blocks of size k. Then a compression function takes k bits of the ith partition and m bits from the previous calculation and calculates m bits of the (i+1)st iteration. The output value of the last iteration (of size m) is the hash value. One common hash function is Message-Digest algorithm 5 (MD5) which generates 128-bit hash values. Flaws were identified in the MD5 algorithm in 1996, leading many organizations to suggest that MD5 may not be relied upon as secure.
The secure hash function SHA was designed by the National Security Agency (NSA) and issued by the National Institute of Standards and Technology (NIST) in 1993 as a Federal Information Standard (FIPS-180). A revised version called SHA-1, which specifies an additional round to the message expansion, was later issued in 1995 as FIPS-180-1. Further revisions to the SHA family of algorithms include SHA-224, SHA-256, SHA-384, and SHA-512 which are occasionally collectively referred to as SHA-2.
SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit string. Given that there are an infinite number of messages that hash to each possible value, there are an infinite number of possible collisions. But because the number of possible hashes is so large, the odds of finding a collision by chance is small (one in 280 to be exact). Thus, using the brute-force method of finding collisions, the success of the attack depends solely on the length of the hash value.
In 2005 Prof. Xiaoyung Wang announced an attack on the NIST SHA-1 hash function and discovered that SHA-1 can be broken. In the same year she created a collision for the MD5 hash function. Prof. Wang's work revealed the vulnerabilities of the two hash functions most widely utilized by industries today. This revelation compelled the NIST to take steps to transition rapidly to the stronger SHA-2 family of hash functions.
By the recommendation of NIST, SHA-1 has been replaced by SHA-256, SHA-384, and SHA-512 (Secure Hash Signature Standard (SHS) (FIPS PUB 180-2)). However, as the algorithms SHA-1, SHA-256, SHA-384, and SHA-512 have common constructions, the same attack that has already been used in the case of SHA-1, can be applied to SHA-256, SHA-384, and SHA-512. Furthermore, there is no guarantee that the attack will not be further enhanced. Hence, all the systems of the SHA family may eventually be compromised.
When a MAC or hashing algorithm is compromised, the conventional recommendation is to abandon the algorithm and move to a more secure algorithm. This requires that electronic infrastructure used to generate the hash or MAC values be updated, which involves moving a large installed base to another system. For obvious reasons, including user inertia, this is a difficult task. Thus, there is a need for methods, computer programs and computer systems that, while utilizing hash and MAC algorithms (such as the MAC algorithms of the SHA family), are operable to provide an improved level of security. There is a further need for the methods, computer programs and computer systems that meet the aforesaid criteria and are further easy to implement to existing technologies and are computationally feasible.
Canadian Patent Application No. 2,546,148 disclose a secure hashing method consisting of: (1) representing an initial sequence of bits as a specially constructed set of polynomials as described herein, (2) transformation of this set by masking, (3) partitioning the transformed set of polynomials into a plurality of classes, (4) forming the bit string during the partitioning, (5) for each of the plurality of classes, factoring each of the polynomials and, so as to define a set of irreducible polynomials, collecting these factors in registers defined for each of the plurality of classes, (6) wrapping the values of the registers from the plurality of classes by means of an enumeration, (7) organizing the enumerations and the bit strings into a knapsack, and, finally, (8) performing an exponentiation in a group to obtain the hash value or the MAC value.
Because of the polynomial representation and masking transformation, in order to create a collision in accordance with the secure hash function described above, an attacker would be required to solve a collection of systems of non-linear iterated exponential equations over a finite field having specific constraints. In the case of a MAC, this difficulty is combined with the difficulty of opening the knapsack, and the difficulty of solving (a) the elliptic curve discrete logarithm referred to below, or (b) the discrete logarithm problem in the finite group, which further contributes to the security of the method of the present invention. As a result of the structure of the procedure, the resulting hash or MAC value has the following important attributes:                a) the length of the output can be changed simply by changing the final step;        b) the computation is a bit-stream procedure as opposed to a block procedure;        c) creating a collision requires the solution to several difficult mathematical problems; and        d) varying some parameters (the number of the bit strings, or the length of the bit strings, for example) allows easy variation of the difficulty of creating a collision.        